﻿% цель (возможные финальные состояния)
final_state([[a],[c,b],[]]).

% функция перехода #1
next_state([Column1, Column2, [Head3|Tail3]], [[Head3|Column1], Column2, Tail3]).
next_state([Column1, Column2, [Head3|Tail3]], [Column1, [Head3|Column2], Tail3]).

next_state([Column1, [Head2|Tail2], Column3], [[Head2|Column1], Tail2, Column3]).
next_state([Column1, [Head2|Tail2], Column3], [Column1, Tail2, [Head2|Column3]]).

next_state([[Head1|Tail1], Column2, Column3], [Tail1, [Head1|Column2], Column3]).
next_state([[Head1|Tail1], Column2, Column3], [Tail1, Column2, [Head1|Column3]]).

% функция перехода #2
% next_state(Stolbs, [Stolb1, [Up1|Stolb2],Rest]) :- delete([Up1|Stolb1], Stolbs, Stolbs1), delete(Stolb2, Stolbs1, Rest).


% поиск решения
search(InitialState, Solution) :- solve_dfs(InitialState, [InitialState], Solution).

% поиск в глубину
solve_dfs(State, Visited, [State]) :- final_state(State).
solve_dfs(State, Visited, [State|Solution]) :-
  next_state(State, NextState),                       % найти следующее состояние
  \+ member(NextState, Visited),                      % проверка на старый путь
  solve_dfs(NextState, [NextState|Visited], Solution).% переход в следующее состояние

% вывод решения на консоль
write_list([Element|Rest]) :- write(Element), nl, write_list(Rest).
write_list([]).

